// https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 使用最小堆维护候选数对，按和排序
// 2. 初始放入(0,0)位置的和
// 3. 每次弹出堆顶最小和，加入右侧和下侧候选
// 4. 避免重复，只在j=0时向下扩展
// 5. 时间复杂度：O(klogk)，空间复杂度：O(k)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <queue>

class Solution 
{
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) 
    {
        int m = nums1.size(), n = nums2.size();

        auto cmp = [](const tuple<int, int, int>& t1, const tuple<int, int, int>& t2){
            return get<0>(t1) > get<0>(t2);
        };
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, decltype(cmp)> minHeap(cmp);
        minHeap.push({nums1[0] + nums2[0], 0, 0});
        
        vector<vector<int>> ret;
        while (k--)
        {
            auto [_, i, j] = minHeap.top();
            minHeap.pop();

            ret.push_back({nums1[i], nums2[j]});

            if (j == 0 && i + 1 < m)
            {
                minHeap.push({nums1[i + 1] + nums2[j], i + 1, 0});
            }

            if (j + 1 < n)
            {
                minHeap.push({nums1[i] + nums2[j + 1], i, j + 1});
            }
        }

        return ret;
    }
};

int main()
{
    vector<int> nums11 = {1,7,11}, nums12 = {2,4,6};
    vector<int> nums21 = {1,1,2}, nums22 = {1,2,3};
    int k1 = 3, k2 = 2;

    Solution sol;

    auto vv1 = sol.kSmallestPairs(nums11, nums12, k1);
    auto vv2 = sol.kSmallestPairs(nums21, nums22, k2);

    for (const auto& v : vv1)
    {
        for (const int& num : v)
        {
            cout << num << " ";
        }
        cout << endl;
    }
    cout << endl;

    for (const auto& v : vv2)
    {
        for (const int& num : v)
        {
            cout << num << " ";
        }
        cout << endl;
    }
    cout << endl;

    return 0;
}